package summary;

import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * @Author: 海琳琦
 * @Date: 2022/4/7 10:55
 * https://leetcode-cn.com/problems/course-schedule-ii/
 */
public class Title210 {

    /**
     * 拓扑排序
     * @param numCourses
     * @param prerequisites
     * @return
     */
    public static int[] findOrder(int numCourses, int[][] prerequisites) {
        Map<Integer, LinkedList<Integer>> graph = new HashMap<>();
        for (int i = 0; i < numCourses; i++) {
            graph.put(i, new LinkedList<>());
        }
        int[] inDegree = new int[numCourses];
        for (int i = 0; i < prerequisites.length; i++) {
            graph.get(prerequisites[i][1]).add(prerequisites[i][0]);
            inDegree[prerequisites[i][0]]++;
        }
        int[] result = new int[numCourses];
        int count = 0;
        LinkedList<Integer> queue = new LinkedList<>();
        for (int i = 0; i < inDegree.length; i++) {
            if (inDegree[i] == 0) {
                result[count++] = i;
                queue.offer(i);
            }
        }
        while (!queue.isEmpty()) {
            Integer course = queue.poll();
            for (Integer nextCourse : graph.get(course)) {
                inDegree[nextCourse]--;
                if (inDegree[nextCourse] == 0) {
                    result[count++] = nextCourse;
                    queue.offer(nextCourse);
                }
            }
        }
        if (count == numCourses) {
            return Arrays.copyOfRange(result, 0, count);
        }else{
            return new int[0];
        }
    }

    static int[] result;

    static int count;

    static int[] inDegree;

    /**
     * dfs
     * @param numCourses
     * @param prerequisites
     * @return
     */
    public static int[] findOrder1(int numCourses, int[][] prerequisites) {
        Map<Integer, LinkedList<Integer>> graph = new HashMap<>();
        for (int i = 0; i < numCourses; i++) {
            graph.put(i, new LinkedList<>());
        }
        inDegree = new int[numCourses];
        for (int i = 0; i < prerequisites.length; i++) {
            graph.get(prerequisites[i][1]).add(prerequisites[i][0]);
            inDegree[prerequisites[i][0]]++;
        }
        int[] visited = new int[numCourses];
        result = new int[numCourses];
        count = numCourses - 1;
        for (int i = 0; i < numCourses; i++) {
            //存在环
            if (!dfs(graph, i, visited)) {
                return new int[0];
            }
        }
        return result;
    }

    private static boolean dfs(Map<Integer,LinkedList<Integer>> graph, int i, int[] visited) {
        if (visited[i] == 1) {
            return false;
        }
        //当前节点被其他路径访问过
        if (visited[i] == 2) {
            return true;
        }
        visited[i] = 1;
        for (Integer nextCourse : graph.get(i)) {
            if (!dfs(graph, nextCourse, visited)) {
                return false;
            }
        }
        visited[i] = 2;
        //一个分支中最深的节点
        result[count--] = i;
        return true;
    }

    public static void main(String[] args) {
        int[][] prerequisites = {{1, 0}};
        findOrder1(2, prerequisites);
    }
}
